package ljl.codetop;

/**
 * 不要求连续，只要求顺序不变的子串是子序列
 *
 * 还没开始做，我已经感觉到不会做了
 */
public class _1143_longest_common_ans {

    /**
     * 肯定是用 dp，这种毫无头绪的题，怎么弄呢
     * 草想不出来放弃了
     */
    static class tryout {

        public int longestCommonSubsequence(String text1, String text2) {
            return 777;
        }
    }

    /**
     * 解法居然这么短...
     */
    static class off1 {
        public int longestCommonSubsequence(String text1, String text2) {
            int m = text1.length(), n = text2.length();
            // 一个空答案是 0 所以不用初始化
            int[][] dp = new int[m + 1][n + 1];
            // 开启两个 for 循环挨个字符比较
            for (int i = 1; i <= m; i++) {
                char c1 = text1.charAt(i - 1);
                for (int j = 1; j <= n; j++) {
                    char c2 = text2.charAt(j - 1);
                    // 某个字符相等，怎么说？公共子序列长度 + 1
                    if (c1 == c2) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }
                    // 当前的两个字符不等，看谁让步？
                    // 什么叫让步？当前的肯定没法 + 1 了因为不等；但是之前的字符是有可能相等的，选更长的作为结果
                    // 为什么不取 dp[i - 1][j - 1]？难道是没必要？
                    else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }
            return dp[m][n];
        }
    }

    static class copy_off1 {
        public int longestCommonSubsequence(String text1, String text2) {
            int l1 = text1.length(), l2 = text2.length();
            int[][] dp = new int[l1 + 1][l2 + 1];
            for (int i = 1; i <= l1; i++) {
                char c = text1.charAt(i - 1);
                for (int j = 1; j <= l2; j++) {
                    if (c == text2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
                    else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
            return dp[l1][l2];
        }
    }
}
